package com.algorithm.ch1.lzr.linkedlist;

import java.util.ArrayList;
import java.util.List;

/**
 * 判断一个链表是否为回文链表(链表指针操作比较薄弱,需要加强)
 * <p>
 * 示例 1:
 * 输入: 1->2
 * 输出: false
 * <p>
 * 示例 2:
 * 输入: 1->2->2->1
 * 输出: true
 *
 * @author lzr
 * @date 2018/8/26
 */
public class IsPalindrome {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(4);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(2);
        ListNode listNode6 = new ListNode(1);
        listNode1.next = listNode2;
        //listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        listNode5.next = listNode6;
        boolean palindrome = isPalindrome1(listNode1);
    }

    /**
     * 使用集合存储val然后首尾进行比较
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome1(ListNode head) {
        //长度为0或1
        if (head == null || head.next == null) {
            return true;
        }
        //长度为2
        if (head.val == head.next.val && head.next.next == null) {
            return true;
        }
        ListNode next = head;
        List<Integer> list = new ArrayList<>();
        while (next != null) {
            list.add(next.val);
            next = next.next;
        }
        int start = 0;
        int end = list.size() - 1;
        while (start < end) {
            if (!list.get(start).equals(list.get(end))) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    /**
     * 更优解决
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome2(ListNode head) {
        //长度为0或1
        if (head == null || head.next == null) {
            return true;
        }
        //长度为2
        if (head.val == head.next.val && head.next.next == null) {
            return true;
        }
        //长度为3及以上
        ListNode slow = head;
        ListNode cur = head.next;
        while (cur.next != null) {
            if (cur.next.val == slow.val) {
                if (cur.next.next != null) {
                    return false;
                }
                cur.next = null;
                slow = slow.next;
                cur = slow.next;
                if (cur == null || slow.val == cur.val) {
                    return true;
                }
            } else {
                cur = cur.next;
            }
        }
        return false;
    }
}
